package com.wangping.algorithm.sort;

import java.util.Arrays;

/**
 * @author wangping
 * @version V1.0
 * @date 2018/11/21 11:14
 */
public class InsertSort {

    /**
     * 插入排序,最简单的整形列表情况
     *
     * @param ints 待排序整形数组
     * @throws NullPointerException 如果传入的数组为null
     */
    public void sort(int[] ints) {
        if (ints.length <= 1) {
            return;
        }
        //不包括第0位,从1开始,对每个元素进行插入
        for (int i = 1; i < ints.length; i++) {
            //待插入数字
            int k = i;
            int sert = ints[i];

            //当试图插入的位置大于0,并且待插入元素比前一个元素小(默认是升序)
            //移动位置,直到待插入元素比前一个元素大,或者到了0
            while (k > 0 && sert < ints[k - 1]) {
                ints[k] = ints[k - 1];
                k--;
            }

            ints[k] = sert;

        }
    }


    public static void main(String[] args) {
        int[] ints = {1, 4, 2, 99, 55, 3, 33, 2, 2, 1, 333, 11};
        InsertSort insertSort = new InsertSort();
        insertSort.sort(ints);
        System.out.println(Arrays.toString(ints));
    }
}
